#include <vector>
#include <iostream>

using namespace std;

class Solution 
{
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) 
    {
        if(matrix.empty())
        {
            return false;
        }
        int m = matrix.size(), n = matrix[0].size();
        int row = 0, col = n - 1;  // 从右上角开始

        while (row < m && col >= 0) {
            if (matrix[row][col] == target) {
                return true;
            } else if (matrix[row][col] > target) {
                col--;  // 当前列太大，左移
            } else {
                row++;  // 当前行太小，下移
            }
        }
        return false;
    }
};

// 辅助函数：打印矩阵
void printMatrix(const vector<vector<int>>& matrix) 
{
    cout << "[";
    for(int i = 0; i < matrix.size(); i++) 
    {
        cout << "[";
        for(int j = 0; j < matrix[i].size(); j++) 
        {
            cout << matrix[i][j];
            if(j < matrix[i].size() - 1) cout << ",";
        }
        cout << "]";
        if(i < matrix.size() - 1) cout << ",";
    }
    cout << "]";
}

int main() 
{
    Solution solution;
    
    // 测试案例1: [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
    cout << "测试案例1:" << endl;
    vector<vector<int>> matrix1 = {
        {1, 4, 7, 11, 15},
        {2, 5, 8, 12, 19},
        {3, 6, 9, 16, 22},
        {10, 13, 14, 17, 24},
        {18, 21, 23, 26, 30}
    };
    int target1 = 5;
    cout << "输入: matrix = ";
    printMatrix(matrix1);
    cout << ", target = " << target1 << endl;
    bool result1 = solution.searchMatrix(matrix1, target1);
    cout << "输出: " << (result1 ? "true" : "false") << endl;
    cout << "期望: true" << endl << endl;
    
    // 测试案例2: 同样的矩阵，target = 14
    cout << "测试案例2:" << endl;
    vector<vector<int>> matrix2 = {
        {1, 4, 7, 11, 15},
        {2, 5, 8, 12, 19},
        {3, 6, 9, 16, 22},
        {10, 13, 14, 17, 24},
        {18, 21, 23, 26, 30}
    };
    int target2 = 14;
    cout << "输入: matrix = ";
    printMatrix(matrix2);
    cout << ", target = " << target2 << endl;
    bool result2 = solution.searchMatrix(matrix2, target2);
    cout << "输出: " << (result2 ? "true" : "false") << endl;
    cout << "期望: true" << endl << endl;
    
    // 测试案例3: 同样的矩阵，target = 20 (不存在)
    cout << "测试案例3:" << endl;
    vector<vector<int>> matrix3 = {
        {1, 4, 7, 11, 15},
        {2, 5, 8, 12, 19},
        {3, 6, 9, 16, 22},
        {10, 13, 14, 17, 24},
        {18, 21, 23, 26, 30}
    };
    int target3 = 20;
    cout << "输入: matrix = ";
    printMatrix(matrix3);
    cout << ", target = " << target3 << endl;
    bool result3 = solution.searchMatrix(matrix3, target3);
    cout << "输出: " << (result3 ? "true" : "false") << endl;
    cout << "期望: false" << endl << endl;
    
    // 测试案例4: 单元素矩阵，存在
    cout << "测试案例4 (单元素矩阵，存在):" << endl;
    vector<vector<int>> matrix4 = {{1}};
    int target4 = 1;
    cout << "输入: matrix = ";
    printMatrix(matrix4);
    cout << ", target = " << target4 << endl;
    bool result4 = solution.searchMatrix(matrix4, target4);
    cout << "输出: " << (result4 ? "true" : "false") << endl;
    cout << "期望: true" << endl << endl;
    
    // 测试案例5: 单元素矩阵，不存在
    cout << "测试案例5 (单元素矩阵，不存在):" << endl;
    vector<vector<int>> matrix5 = {{1}};
    int target5 = 2;
    cout << "输入: matrix = ";
    printMatrix(matrix5);
    cout << ", target = " << target5 << endl;
    bool result5 = solution.searchMatrix(matrix5, target5);
    cout << "输出: " << (result5 ? "true" : "false") << endl;
    cout << "期望: false" << endl << endl;
    
    // 测试案例6: 单行矩阵
    cout << "测试案例6 (单行矩阵):" << endl;
    vector<vector<int>> matrix6 = {{1, 3, 5, 7, 9}};
    int target6 = 5;
    cout << "输入: matrix = ";
    printMatrix(matrix6);
    cout << ", target = " << target6 << endl;
    bool result6 = solution.searchMatrix(matrix6, target6);
    cout << "输出: " << (result6 ? "true" : "false") << endl;
    cout << "期望: true" << endl << endl;
    
    // 测试案例7: 单列矩阵
    cout << "测试案例7 (单列矩阵):" << endl;
    vector<vector<int>> matrix7 = {{1}, {3}, {5}, {7}, {9}};
    int target7 = 7;
    cout << "输入: matrix = ";
    printMatrix(matrix7);
    cout << ", target = " << target7 << endl;
    bool result7 = solution.searchMatrix(matrix7, target7);
    cout << "输出: " << (result7 ? "true" : "false") << endl;
    cout << "期望: true" << endl << endl;
    
    // 测试案例8: 小矩阵，目标在左上角
    cout << "测试案例8 (目标在左上角):" << endl;
    vector<vector<int>> matrix8 = {{1, 3}, {2, 4}};
    int target8 = 1;
    cout << "输入: matrix = ";
    printMatrix(matrix8);
    cout << ", target = " << target8 << endl;
    bool result8 = solution.searchMatrix(matrix8, target8);
    cout << "输出: " << (result8 ? "true" : "false") << endl;
    cout << "期望: true" << endl << endl;
    
    // 测试案例9: 小矩阵，目标在右下角
    cout << "测试案例9 (目标在右下角):" << endl;
    vector<vector<int>> matrix9 = {{1, 3}, {2, 4}};
    int target9 = 4;
    cout << "输入: matrix = ";
    printMatrix(matrix9);
    cout << ", target = " << target9 << endl;
    bool result9 = solution.searchMatrix(matrix9, target9);
    cout << "输出: " << (result9 ? "true" : "false") << endl;
    cout << "期望: true" << endl << endl;
    
    // 测试案例10: 空矩阵
    cout << "测试案例10 (空矩阵):" << endl;
    vector<vector<int>> matrix10 = {};
    int target10 = 1;
    cout << "输入: matrix = []";
    cout << ", target = " << target10 << endl;
    bool result10 = solution.searchMatrix(matrix10, target10);
    cout << "输出: " << (result10 ? "true" : "false") << endl;
    cout << "期望: false" << endl << endl;
    
    return 0;
}